#include <algorithm>
#include <bitset>
#include "./Markup/Markup.h"
#include "StdAfx.h"
#include "Permutation.h"
#include <string>
#include <iostream>
using namespace std;


//this is for disabling a visual studio warning about a potenaly 
//unsafe use of funcation std::copy
#pragma warning(disable:4996)

//--------------------------------------------------------------------------
// == Operator for RelatedPermutation (compares indexes)
//--------------------------------------------------------------------------
bool RelatedPermutation::operator==(const RelatedPermutation &other) const
{
	if (this==&other)
	{
		return true;
	}	

	return (this->GetIndex())==(other.GetIndex());
}

//--------------------------------------------------------------------------
// != operator for RelatedPermutation (compares indexes)
//--------------------------------------------------------------------------
bool RelatedPermutation::operator!=(const RelatedPermutation &other) const
{
	return !((*this)==other);
}

//--------------------------------------------------------------------------
// Save: Saves permutaion index to XML
// Parameters:
// xml - output xml
//--------------------------------------------------------------------------
void RelatedPermutation::Save(CMarkup &xml)
{
	xml.AddChildElem(RELATED_PERMUTATION_XML, m_GroupIndex);
}
//--------------------------------------------------------------------------
//--------------------------------------------------------------------------
//--------------------------------------------------------------------------

// Permutation

// Public functions 

Permutation::Permutation(unsigned long *permutationList,int wordLen, int groupSize, int name)
: m_WordLen(wordLen), m_GroupSize(groupSize), m_Permutation(permutationList), m_GroupIndex(name)
{}

Permutation::Permutation(unsigned long *permutationList,int wordLen = 1, int groupSize = 1)
: m_WordLen(wordLen), m_GroupSize(groupSize), m_Permutation(permutationList), m_GroupIndex(-1)
{}

Permutation::~Permutation(void)
{}


//--------------------------------------------------------------------------
// CountIntersection : Receives  int arrays and counts how many elements are 
//								 in the intersection between it and the 
//								 current perm
// Parameters:
// groupB - permutation as unsigned longs
// groupBrows - how many rows are in groupB
//--------------------------------------------------------------------------
int Permutation::CountIntersection(unsigned long* groupB, int groupBrows)
{
	int intersectionSize = 0;

	for (int i=0; i<m_GroupSize; i++)
	{	
		for (int j=0; j<groupBrows; j++)
		{
			if (m_Permutation[i]==groupB[j])
			{	
				intersectionSize++;
			}
		}
	}
	return intersectionSize;
}

//--------------------------------------------------------------------------
// GetMatrixColumns: Returns a new matrix which is the column matrix for this
//                   one
//--------------------------------------------------------------------------
unsigned long* Permutation::GetMatrixColumns() const
{
	return TransposeMatrixBits(m_GroupSize,m_WordLen);
}

//--------------------------------------------------------------------------
// GetMatrixColumns: Returns a new matrix which is the column matrix for this
//                   one
//--------------------------------------------------------------------------
unsigned long* Permutation::GetMatrixRows() const
{
	return m_Permutation;
}

//--------------------------------------------------------------------------
// UpdateMatrix: Updates permutation matrix
// Parameters:
// newPerm - new matrix (list of longs - rows)
// newGroupSize - how many rows in new matrix
//--------------------------------------------------------------------------
void Permutation::UpdateMatrix(unsigned long* newPerm, int newGroupSize)
{
	m_GroupSize = newGroupSize;
//	delete m_Permutation;
	m_Permutation = newPerm;
}

//--------------------------------------------------------------------------
// GetGroupSize: Returns group size
//--------------------------------------------------------------------------
int Permutation::GetGroupSize() const
{
	return m_GroupSize;
}



//--------------------------------------------------------------------------
// GetMatrixWithoutIntersection : Removes the intersection between 2 matrices
//                                from one and returns the clean matrix
// Parameters:
// matrixToClean - matrix to remove intersection from
// matrixToCleanRows - how many rows in matrixToClean
// otherMatrix - matrix to check intersection with
// otherMatrixRows - how many rows in otherMatrix
// intersectionSize - how many intersecting rows both matrices have
// Returns: pointer to new unsigned long array without intersection
//--------------------------------------------------------------------------
 unsigned long* Permutation::GetMatrixWithoutIntersection(unsigned long* matrixToClean, int matrixToCleanRows, unsigned long* otherMatrix, int otherMatrixRows, int intersectionSize)
{
	// If permutations are the same, nothing to do
	if (intersectionSize == 0)
	{
		return matrixToClean;
	}

	// If we are cleaning the whole matrix, return NULL
	if (matrixToCleanRows == intersectionSize)
	{
		return NULL;
	}

	unsigned long* resultMatrix = new unsigned long[matrixToCleanRows - intersectionSize];

	int copiedRows = 0;

	for (int i=0; i < matrixToCleanRows; i++)
	{
		bool copyRow = true;
		int j=0;
		while (j< otherMatrixRows && copyRow)
		{
			if (otherMatrix[j] == matrixToClean[i])
			{
				copyRow = false;
			}
			j++;
		}
		if (copyRow)
		{
			resultMatrix[copiedRows] = matrixToClean[i];
			copiedRows++;
		}
	}
	
	return resultMatrix;
}

//--------------------------------------------------------------------------
// NextPermutation: Returns the next permutation on columns
//--------------------------------------------------------------------------
Permutation *Permutation::NextPermutation()
{
	int columCount = m_WordLen;
	int rowCount = m_GroupSize;
	unsigned long *columns = GetMatrixColumns();

	//convert the columns array to a vector data structure
	std::vector<unsigned long> columnsVector(columns, columns + columCount);
	 
	//clac next permutation on the columns of the metrix
	std::vector<unsigned long>::iterator start = columnsVector.begin();
	std::vector<unsigned long>::iterator end = columnsVector.end();
	if (!std::next_permutation(start, end))
	{
		delete columns;
		return NULL; // reched the last permutaion
	}

	//convert the colmns vector back to an array
	std::copy(start,end,columns);

	// trnspose the result to return to the original matrix

	Permutation* newPermutaion = new Permutation(columns, rowCount, columCount);
	unsigned long *temp = newPermutaion->GetMatrixColumns();
	// Delete duplicate rows
	newPermutaion->m_GroupSize = CleanPermutation(temp,rowCount);
	newPermutaion->m_Permutation = temp;
	newPermutaion->m_WordLen = columCount;
		 
	delete columns;
	return newPermutaion;
}

 //--------------------------------------------------------------------------
 // operator==
 //--------------------------------------------------------------------------
 bool Permutation::operator== (const Permutation &other) const
 {
	 if (this == &other)
	 {	
		return true;
	 }

	if (m_GroupSize != other.GetGroupSize())
	{
		return false;
	}

	for (int i=0; i<m_GroupSize; i++)
	{
		int j=0;
		bool found = false;
		while (j< m_GroupSize && !found)
		{
			if (m_Permutation[i] == (other.GetMatrixRows()[j]))
			{
				found = true;
			}
			else 
			{
				j++;
			}
		}
		// if we went over all the other array and still didn't find
		// this item - they're not equal
		if (!found)
		{
			return false;
		}
	}

	return true;
 }

 //--------------------------------------------------------------------------
 // operator!=
 //--------------------------------------------------------------------------
 bool Permutation::operator!= (const Permutation &other) const
 {
	return !(*this==other);
 }

 //--------------------------------------------------------------------------
 // AddRelatedPerm: Add a permutation as related to this one
 // Parameters:
 // other - permutation to link to this one
 //--------------------------------------------------------------------------
 void Permutation::AddRelatedPerm(RelatedPermutation other)
 {
	 m_RelatedPerms.push_back(other);
 }

 //--------------------------------------------------------------------------
 // Clone:  Returns a new Permutation object - a copy of the original matrix 
 //         (without related permutations)
 //--------------------------------------------------------------------------
 Permutation* Permutation::Clone() const
 {
	int matrixSize = sizeof(unsigned long)*m_GroupSize; // how many bytes to copy
	unsigned long* matrixCopy = new unsigned long[m_GroupSize];
	memcpy(matrixCopy,m_Permutation,matrixSize);
	Permutation* newPerm = new Permutation(matrixCopy,m_WordLen,m_GroupSize,m_GroupIndex);
	return newPerm;
 }

 //--------------------------------------------------------------------------
 // SaveToXml - Saves to an XML object
 // Format: <group name=m_GroupIndex total=m_GroupSize><vertex>vertex name</vertex></group>
 //---------------------------------------------------------------------------
 void Permutation::SaveToXml(CMarkup &xml) const
 {
	 xml.AddChildElem(GROUP_XML);
	 xml.IntoElem();
	 xml.AddAttrib(GROUP_NAME_XML,m_GroupIndex);
	 xml.AddAttrib(GROUP_SIZE_XML,m_GroupSize);
	 for (int i=0; i<m_GroupSize; i++)
	 {
		 // Go over all words and save them in binary form
		 xml.AddChildElem(VERTEX_XML,GetVertexNameString(*(m_Permutation+i)));
	 }
	 xml.OutOfElem();
 }


 //--------------------------------------------------------------------------
 // SaveRelatedPermsToXml : Goes over the related perms and saves the indexes
 //                         to xml
 // Parameters:
 // xml - output xml
 //--------------------------------------------------------------------------
 void Permutation::SaveRelatedPermsToXml(CMarkup &xml)
 {
	 xml.AddChildElem(RELATED_PERMUTATIONS_XML);
	 xml.IntoElem();
	 for (vector<RelatedPermutation>::iterator it = m_RelatedPerms.begin(); it < m_RelatedPerms.end(); it++)
	 {
		 (*it).Save(xml);	
	 }
	 xml.OutOfElem();
 }

// end Public

// Private functions 


//--------------------------------------------------------------------------
// TransposeMatrixBits : Returns the matrix transposed
// Parameters:
// rowCount
// colCount
// Returns:
// New int array, 1  int for each column. Leftmost column is 1st int.
//--------------------------------------------------------------------------
unsigned long* Permutation::TransposeMatrixBits(const int rowCount, const int colCount) const
{
	unsigned long *transMatrix = new unsigned long[colCount];
	
	for (int i = 0; i < colCount ; i++)
	{
		transMatrix[i] = 0;
	}

	// Go over each one of the numbers
	for (int i = 0; i < rowCount; i++)
	{
		int currentNumber = m_Permutation[i];
		// and place its bits in the right places in the column array
		for (int j = colCount-1 ; j >= 0 ; j--)
		{
			int currentBit = currentNumber & 1; // Get last bit
			currentNumber = currentNumber >> 1; // Shift right to deal with next bit
			transMatrix[j] = (transMatrix[j] << 1)+currentBit; // Shift the previous bit to the left (it is a left-er column) and add
		}
	}
	return transMatrix;
}

//-------------------------------------------------------------------------
// GetVertexNameString - Returns string for vertex name in m_Wordlen bits
//-------------------------------------------------------------------------
string Permutation::GetVertexNameString(unsigned long vertex) const
{
  bitset <sizeof( unsigned long ) * 8> bits( vertex );
  string result = bits.to_string();
  
  return result.substr(result.length()-m_WordLen,m_WordLen);
}

//-------------------------------------------------------------------------
// CleanPermutation: Removes duplicates from permutation and returns new
//                   size
// Parameters:
// perm - permutation to be cleaned
// size - current permutation size
//-------------------------------------------------------------------------
int Permutation::CleanPermutation(unsigned long *perm, int size)
{
	int newSize = 0;
	vector<unsigned long> rowsToCopy;

	for (int i = 0; i<size; i++)
	{
		bool found = false;
		for (int j=i+1; j<size && !found; j++)
		{
			if (perm[i] == perm[j])
			{
				found = true;
			}
		}
		// If not found - copy this row
		if (!found)
		{
			newSize++;
			rowsToCopy.push_back(perm[i]);
		}
	}

	vector<unsigned long>::iterator start = rowsToCopy.begin();
	vector<unsigned long>::iterator end = rowsToCopy.end();
	unsigned long *newPerm = new unsigned long[newSize];

	// Copy the rows back to an array
	std::copy(start,end,newPerm);

	perm = newPerm;

	return newSize;
}

// end  Private
